// 1. 封装一个节点Node
class Node<T> {
  value: T;
  next: Node<T> | null = null;
  constructor(value: T) {
    this.value = value;
    this.next = null;
  }
}
// 2. 封装一个链表LinkedList
//    1.一个链表长度 2.一个head

class LinkedList<T> {
  private head: Node<T> | null = null;
  private size: number = 0;

  // 获取 current的节点
  private getPositionNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;

    while (index++ < position && current) {
      current = current.next;
    }
    return current ?? null;
  }

  // 1. append方法
  append(value: T) {
    // 1.1 给value创建node节点
    const newNode = new Node(value);
    // 1.2 判断链表是否为空
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }

      // 最后，current是最后一个node节点
      current.next = newNode;
    }
    // 链表长度
    this.size++;
  }
  // 2. 为了查看链表：遍历链表
  traverse() {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }

    console.log(values.join(' -> '));
  }
  // 3. 插入方法
  insert(value: T, position: number): boolean {
    // 1. 插入的位置需要边界判断
    if (position < 0 || position >= this.size) return false;
    // 2. 插入数据
    const newNode = new Node(value);
    //   2.1. 添加到第一个位置：索引为0
    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      // 前一个节点
      let previous = this.getPositionNode(position - 1);
      // previous!.next -> current
      newNode.next = previous!.next ?? null;
      previous!.next = newNode;
    }

    // 3. size改变
    this.size++;
    return true;
  }
  // 4. 根据位置移除节点
  removeAt(position: number): T | null {
    // 4.1 越界判断
    if (position < 0 || position >= this.size) return null;
    // 4.2 根据位置移除节点

    let current = this.head;

    if (position === 0) {
      this.head = current?.next ?? null;
    } else {
      let previous = this.getPositionNode(position - 1);
      current = previous?.next ?? null;
      previous!.next = previous?.next?.next ?? null;
    }
    // 4.3 改变size
    this.size--;

    return current!.value ?? null;
  }
  // 8. remove根据内容从链表中移除一项
  remove(element: T): boolean {
    const index = this.indexOf(element);
    if (index === -1) return false;
    return !!this.removeAt(index);
  }
  // 5. 获取方法:获取对应位置的元素
  get(position: number): T | null {
    //  越界判断;
    if (position < 0 || position >= this.size) return null;

    const currentNode = this.getPositionNode(position);
    return currentNode?.value ?? null;
  }
  // 6. 修改某个位置的元素
  update(position: number, value: T): boolean {
    if (position < 0 || position >= this.size) return false;
    const current = this.getPositionNode(position);
    if (current) current.value = value;
    return true;
  }
  // 7. 返回元素在链表中的索引**。如果链表中没有该元素则返回-1。
  indexOf(element: T): number {
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.value === element) {
        return index;
      }
      index++;
      current = current.next;
    }

    return -1;
  }
  // 9.如果链表中不包含任何元素，返回true，
  isEmpty(): boolean {
    return !this.size;
  }
  // 10. 返回链表包含的元素个数。与数组的length属性类似
  get length() {
    return this.size;
  }
}

export { LinkedList };
